package com.leetcode.August;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 全排列
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-02 10:01
 */
public class fullPerm {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        backtrack(res, temp, nums);
        return res;
    }
        private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
        if (nums.length==tempList.size()){ result.add(tempList);}
        else{
            for (int num : nums) {
                if (tempList.contains(num)) continue;
                tempList.add(num);
                backtrack(result, tempList, nums);
                tempList.remove(tempList.size()-1);
            }
        }

        }
}
/**接下来调用递归函数 backtrack，这一步非常关键。在这个递归调用中，我们传递了三个参数：

 result: 结果列表，用来收集所有可能的全排列。
 tempList: 当前正在构建的排列。
 nums: 原始数组。
 递归调用会继续填充 tempList 直到其大小与 nums 的大小相同。当 tempList 的大小等于 nums 的长度时，说明已经找到一个完整的排列，
 并且会将这个排列添加到 result 列表中。

 5. tempList.remove(tempList.size() - 1);
 这是回溯步骤。当我们完成了一次递归调用后，需要将最后添加的数字 num 从 tempList 中移除，以便下一次迭代可以尝试不同的数字。
 这样，我们可以确保每次迭代都尝试不同的数字，直到找到所有的排列。*/
